{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Coins You Can Get"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #math #game-theory #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #数学 #博弈 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxCoins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你可以获得的最大硬币数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每一轮中，你将会选出 <strong>任意</strong> 3 堆硬币（不一定连续）。</li>\n",
    "\t<li>Alice 将会取走硬币数量最多的那一堆。</li>\n",
    "\t<li>你将会取走硬币数量第二多的那一堆。</li>\n",
    "\t<li>Bob 将会取走最后一堆。</li>\n",
    "\t<li>重复这个过程，直到没有更多硬币。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数数组 <code>piles</code> ，其中 <code>piles[i]</code> 是第 <code>i</code> 堆中硬币的数目。</p>\n",
    "\n",
    "<p>返回你可以获得的最大硬币数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>piles = [2,4,1,2,7,8]\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>选出 (2, 7, 8) ，Alice 取走 8 枚硬币的那堆，你取走 <strong>7</strong> 枚硬币的那堆，Bob 取走最后一堆。\n",
    "选出 (1, 2, 4) , Alice 取走 4 枚硬币的那堆，你取走 <strong>2</strong> 枚硬币的那堆，Bob 取走最后一堆。\n",
    "你可以获得的最大硬币数目：7 + 2 = 9.\n",
    "考虑另外一种情况，如果选出的是 (1, <strong>2</strong>, 8) 和 (2, <strong>4</strong>, 7) ，你就只能得到 2 + 4 = 6 枚硬币，这不是最优解。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>piles = [2,4,5]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>piles = [9,8,7,6,5,1,2,3,4]\n",
    "<strong>输出：</strong>18\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= piles.length &lt;= 10^5</code></li>\n",
    "\t<li><code>piles.length % 3 == 0</code></li>\n",
    "\t<li><code>1 &lt;= piles[i] &lt;= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-coins-you-can-get](https://leetcode.cn/problems/maximum-number-of-coins-you-can-get/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-coins-you-can-get](https://leetcode.cn/problems/maximum-number-of-coins-you-can-get/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,1,2,7,8]', '[2,4,5]', '[9,8,7,6,5,1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)//3\n",
    "        for i in range(len(piles)):\n",
    "            piles[i] *= -1\n",
    "        result = 0\n",
    "        heapify(piles)\n",
    "        for i in range(n):\n",
    "            heapq.heappop(piles)\n",
    "            result += -heapq.heappop(piles)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse=True)\n",
    "        n = len(piles)\n",
    "        ans=0\n",
    "        for i in range(1,n//3*2,2):\n",
    "            ans+=piles[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        if not piles:\n",
    "            return 0\n",
    "        piles = sorted(piles, reverse=True)\n",
    "        group_sum = 2 * (len(piles) / 3)\n",
    "        piles = piles[:int(group_sum)]\n",
    "        res = piles[1::2]\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "\n",
    "        n = len(piles)\n",
    "        piles.sort()\n",
    "        return sum(piles[n // 3 :: 2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n=len(piles)//3\n",
    "        ans=0\n",
    "        p=sorted(piles,reverse=True)\n",
    "        for i in range(n):\n",
    "            ans+=p[1+2*i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n3=len(piles)\n",
    "        n=n3//3\n",
    "        ans=0\n",
    "        p=sorted(piles,reverse=True)\n",
    "        for i in range(n):\n",
    "            ans+=p[1+2*i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles) // 3\n",
    "        return sum([piles[i] for i in range(n, len(piles), 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles) // 3\n",
    "        return sum([piles[i] for i in range(n, len(piles), 2)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n=len(piles)//3\n",
    "        ans=0\n",
    "        p=sorted(piles,reverse=True)\n",
    "        for i in range(n):\n",
    "            ans+=p[1+2*i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        return sum(\n",
    "            piles[-2 * i]\n",
    "            for i in range(1, len(piles) // 3 + 1)\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        num=0\n",
    "        for i in range((len(piles)//3),len(piles),2):\n",
    "            num+=piles[i]\n",
    "        return num\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n3=len(piles)\n",
    "        n=n3//3\n",
    "        ans=0\n",
    "        p=sorted(piles,reverse=True)\n",
    "        for i in range(n):\n",
    "            ans+=p[1+2*i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse=True)\n",
    "        ret = 0\n",
    "        for i in range(len(piles)//3):\n",
    "            ret += piles[2*i+1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: list[int]) -> int:\n",
    "        ret = 0\n",
    "        piles.sort()\n",
    "        for i in range(len(piles)//3, len(piles) ,2):\n",
    "            ret = ret + piles[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        piles.sort()\n",
    "        j = n-2\n",
    "        k = n//3\n",
    "        ans = 0\n",
    "        # cur = piles[n-1]\n",
    "        while k:\n",
    "            ans += piles[j]\n",
    "            j -= 2\n",
    "            k -=1\n",
    "            # print(ans,j,cur,piles[j])\n",
    "            # if cur>piles[j] and piles[j]>piles[j-1]:\n",
    "            #     ans += piles[j]\n",
    "            #     cur = piles[j-1]\n",
    "            #     j -= 2\n",
    "            # elif piles[j]==cur:\n",
    "            #     ans += cur\n",
    "            #     cur = piles[j-1]\n",
    "            #     j -= 2\n",
    "            # elif piles[j] == piles[j-1]:\n",
    "            #     ans += piles[j]\n",
    "            #     j -= 2\n",
    "            # k -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse = True)\n",
    "        n = len(piles)//3\n",
    "        res = 0\n",
    "        for i in range(1, n*2+1, 2):\n",
    "            res += piles[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        ans = 0\n",
    "        for i in range(n//3):\n",
    "            ans += piles[n-2-i*2]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = 0\n",
    "        piles.sort()\n",
    "        for i in range(int(len(piles)/3),len(piles),2):\n",
    "            n += piles[i]\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        ans = 0\n",
    "        for i in range(n // 3, n, 2):\n",
    "            ans += piles[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        a = sorted((piles))\n",
    "        print(a)\n",
    "        z = len(piles) // 3\n",
    "        k = 0\n",
    "        while z < len(piles):\n",
    "            k += a[z]\n",
    "            z += 2\n",
    "        return(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        \n",
    "        num_piles = len(piles)\n",
    "        sum_ = 0\n",
    "        for idx in range(num_piles//3, num_piles, 2):\n",
    "            sum_ += piles[idx]\n",
    "        return sum_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        ans=0\n",
    "        piles.sort()\n",
    "        n=len(piles)//3\n",
    "        for i in range(n):\n",
    "            ans+=piles[n+2*i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        a = sorted((piles))\n",
    "        print(a)\n",
    "        z = len(piles) // 3\n",
    "        k = 0\n",
    "        while z < len(piles):\n",
    "            k += a[z]\n",
    "            z += 2\n",
    "        return(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles = sorted(piles, reverse=True)\n",
    "        print(piles)\n",
    "        c = 0\n",
    "        n = int(len(piles) / 3)\n",
    "        for i in range(1, 2 * n, 2):\n",
    "            c += piles[i]\n",
    "        print(c)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        # lst = [9,8,7,6,5,1,2,3,4]\n",
    "        # lst.sort()\n",
    "        # print(lst)\n",
    "        piles.sort()\n",
    "\n",
    "        size = len(piles)\n",
    "        idx = size // 3\n",
    "        res = 0\n",
    "        while idx < size:\n",
    "            res += piles[idx]\n",
    "            idx += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        m = len(piles)-1-1\n",
    "        b = asum = 0\n",
    "        while b < m:\n",
    "            asum += piles[m]\n",
    "            m -= 2\n",
    "            b += 1\n",
    "        return asum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        return sum(sorted(piles)[len(piles)//3::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        ans = 0\n",
    "        j = n - 2\n",
    "        for i in range(n // 3):\n",
    "            ans += piles[j]\n",
    "            j -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        result, n = 0, len(piles)\n",
    "        for i in range(n // 3, n, 2):\n",
    "            result += piles[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)//3  # yi ge ren  qu  d ge shu\n",
    "        piles = piles[n:]\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i < len(piles):\n",
    "            ans += piles[i]\n",
    "            i += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "\n",
    "        piles.sort()\n",
    "\n",
    "        n = len(piles) // 3\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            ind = len(piles) - 2 - i * 2\n",
    "            res += piles[ind]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "      n = len(piles) // 3\n",
    "      piles.sort(reverse=True)\n",
    "      return sum(piles[i] for i in range(1, 2 * n, 2))\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        # a,b,c三个人, 每次a拿最大的,b拿第二大,c拿最小的\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        b,c = n-2, 0\n",
    "        ans = 0\n",
    "        # 只要看b和c的就可以了,把a省略了\n",
    "        while c < b:\n",
    "            ans += piles[b]\n",
    "            b -= 2\n",
    "            c += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        s=sum(piles[len(piles)//3:][::2])\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        ans = 0\n",
    "        n = len(piles)\n",
    "        for i in range(n-1, n // 3, -2):\n",
    "            ans += piles[i-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        result = 0\n",
    "        n = len(piles) // 3\n",
    "        for i in range(n):\n",
    "            result += piles[i*-2 -2]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        len_piles = len(piles)\n",
    "        piles = sorted(piles)\n",
    "        j = len_piles -2\n",
    "        count = 0\n",
    "        while j > len_piles // 3 - 1:\n",
    "            count += piles[j]\n",
    "            j -= 2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        piles.sort()\n",
    "        return sum(piles[n // 3 :: 2])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        sum1 = 0\n",
    "        n  = len(piles)//3\n",
    "        return(sum(piles[n::2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n=len(piles)\n",
    "        return sum(piles[n//3:n:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        len_p = len(piles)\n",
    "        stop = len_p // 3\n",
    "\n",
    "        piles = sorted(piles, reverse = True)\n",
    "        sum_ = 0\n",
    "        times = 0\n",
    "\n",
    "        if len_p == 3:\n",
    "            return piles[1]\n",
    "\n",
    "        for i in range(1, len_p-2, 2):\n",
    "            sum_ += piles[i]\n",
    "            times += 1\n",
    "            if times == stop:\n",
    "                break\n",
    "\n",
    "        return sum_\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles=sorted(piles)\n",
    "        k=int(len(piles)/3)\n",
    "        return sum(piles[k::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles = sorted(piles)\n",
    "        n = len(piles) // 3\n",
    "        \n",
    "        return sum(piles[n::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles = sorted(piles)[len(piles) // 3:]\n",
    "        return sum([piles[n] for n in range(len(piles)) if n % 2 == 0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quick_sort(self, arr):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        pivot = arr[len(arr)//2] \n",
    "        left = [x for x in arr if x > pivot]\n",
    "        right = [x for x in arr if x < pivot]\n",
    "        middle = [x for x in arr if x == pivot]\n",
    "        return self.quick_sort(left)+middle+self.quick_sort(right)\n",
    "\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        t = len(piles)//3\n",
    "        s = 0 \n",
    "        arr = self.quick_sort(piles)\n",
    "        for i in range(t):\n",
    "            s = s + arr[i*2 + 1]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        from queue import Queue\n",
    "        buckets = [Queue() for i in range(10)]\n",
    "        n = 1\n",
    "        while 1:\n",
    "            flag = False\n",
    "            for i in range(len(piles)):\n",
    "                index = int(piles[i]/n%10)\n",
    "                buckets[index].put(piles[i])\n",
    "                if piles[i] < n:\n",
    "                    continue\n",
    "                flag =True\n",
    "\n",
    "            if not flag:\n",
    "                break\n",
    "            piles = []\n",
    "            for i in range(len(buckets)):\n",
    "                while not buckets[i].empty():\n",
    "                    piles.append(buckets[i].get())\n",
    "            n *= 10\n",
    "        print(piles)\n",
    "        max_num = 0\n",
    "        for i in range(int(len(piles)/3)):\n",
    "            max_num += piles[-(i+1)*2]\n",
    "        return max_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n=len(piles)//3\n",
    "        piles.sort()\n",
    "        ans=0\n",
    "        for i in range(1,n+1):\n",
    "            ans+=piles[3*n-2*i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse = True)\n",
    "        end = int(len(piles) /3) *2\n",
    "        res = sum(piles[1:end:2])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        piles.sort()\n",
    "        return sum(piles[n // 3 :: 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        ans = 0\n",
    "        n = len(piles)//3\n",
    "        for i in range(-2,-2*n-2,-2):\n",
    "            ans += piles[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse=True)\n",
    "        n = len(piles)\n",
    "        result = 0\n",
    "        for i in range(1, n * 2 // 3, 2):\n",
    "            result += piles[i]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        piles.sort()\n",
    "        return sum(piles[n // 3 :: 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse=True)\n",
    "        n = len(piles) // 3\n",
    "        ans = 0\n",
    "        for i in range(1, n*2+1, 2):\n",
    "            ans += piles[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        \n",
    "        \"\"\"\n",
    "        before sort: [2, 4, 1, 2, 7, 8]\n",
    "        after sort:  [1, 2, 2, 4, 7, 8]\n",
    "        \n",
    "                         B        U  A  (1st)\n",
    "                      B     U  A        (2nd)\n",
    "                            *(從這裡開始每隔兩個取)\n",
    "        len(piles) = 6 = 3*2\n",
    "        \"\"\"\n",
    "        \n",
    "        piles.sort()\n",
    "        n = len(piles) // 3\n",
    "        \n",
    "        max_coin = 0   \n",
    "        for i in range(n, len(piles), 2):\n",
    "            max_coin += piles[i]\n",
    "        return max_coin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        piles.sort()\n",
    "        return sum(piles[n // 3 :: 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse=True)\n",
    "        if len(piles) == 3:\n",
    "            return piles[1]\n",
    "        n = len(piles) // 3\n",
    "        count = 0\n",
    "        res = 0\n",
    "        for i in range(len(piles)):\n",
    "            if i % 2 == 0:\n",
    "                continue\n",
    "            else:\n",
    "                count += 1\n",
    "                res += piles[i]\n",
    "            if count == n:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        ans = 0\n",
    "        for i in range(n//3):\n",
    "            ans += piles[n-2-i*2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        t = n//3\n",
    "        res = 0\n",
    "        flag = True\n",
    "        for i in range(t, n):\n",
    "            if flag == True:\n",
    "                res += piles[i]\n",
    "                flag = False\n",
    "            else:\n",
    "                flag = True\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)\n",
    "        list.sort(piles)\n",
    "        res = 0\n",
    "        cnt = n//3\n",
    "        \n",
    "        for i in range(cnt):\n",
    "            res += piles[n-2-2*i]\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort(reverse=True)\n",
    "        if len(piles) == 3:\n",
    "            return piles[1]\n",
    "        n = len(piles) // 3\n",
    "        res = 0\n",
    "        for i in range(len(piles)):\n",
    "            if i % 2 == 0:\n",
    "                continue\n",
    "            else:\n",
    "                n -= 1\n",
    "                res += piles[i]\n",
    "            if n <= 0:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        l=len(piles)\n",
    "        res=0\n",
    "        for i in range(l//3):\n",
    "            #print(l-2*i-2)\n",
    "            res+=piles[l-2*i-2]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        return sum(sorted(piles, reverse=True)[1:len(piles) * 2 // 3:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles.sort()\n",
    "        n = len(piles)\n",
    "        n_1 = n/3\n",
    "        piles_1 = []\n",
    "        for i in range(int((n*2)/3)):\n",
    "            piles_1.append(piles[int(i+n/3)])\n",
    "        res = 0\n",
    "        for i in range(int((n*2)/3)):\n",
    "            if i%2 == 0:\n",
    "                res+=piles_1[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        return sum(sorted(piles)[len(piles) // 3::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxCoins(self, piles: List[int]) -> int:\n",
    "    return sum(sorted(piles)[len(piles)//3::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        n = len(piles)//3\n",
    "        piles = sorted(piles, reverse=True)\n",
    "        return sum(piles[1:2*n:2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        piles = sorted(piles,reverse=True)\n",
    "        r=0\n",
    "        for i in range(len(piles)):\n",
    "            if i>=len(piles)/3*2:\n",
    "                break\n",
    "            if i%2:\n",
    "                r += piles[i]\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def maxCoins(self, piles: List[int]) -> int:\n",
    "    return sum(sorted(piles)[len(piles)//3::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        return sum(sorted(piles)[-2:-len(piles)//3*2-1:-2])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        return sum(sorted(piles)[len(piles)//3::2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxCoins(self, piles: List[int]) -> int:\n",
    "        return sum(sorted(piles, reverse=True)[1:len(piles) // 3 * 2:2])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
